package 二叉树;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

public class JZ36二叉搜索树与双向链表 {

    /**
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。
     * 要求不能创建任何新的节点，只能调整树中节点指针的指向。
     * 为了让您更好地理解问题，以下面的二叉搜索树为例：
     * 我们希望将这个二叉搜索树转化为双向循环链表。
     * 链表中的每个节点都有一个前驱和后继指针。
     * 对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
     * 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
     * 特别地，我们希望可以就地完成转换操作。
     * 当转化完成以后，树中节点的左指针需要指向前驱，
     * 树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
     */

    public Node treeToDoublyList(Node root) {

        if(root==null||(root.right==null&&root.left==null)){
            return root;
        }

        List<Node> list=new ArrayList<>();
        dfs(root,list);

        if(list.size()==1){
            return root;
        }

        System.out.println(JSON.toJSONString(list));

        Node head=list.get(0);
        Node tail=list.get(list.size()-1);

        //准备首尾
        tail.left=list.get(list.size()-2);
        tail.right=head;
        head.left=tail;
        head.right=list.get(1);

        for (int i = 1; i < list.size()-1; i++) {

            Node cur=list.get(i);
            cur.left=list.get(i-1);
            cur.right=list.get(i+1);

        }

        return head;
    }

    private void dfs(Node node,List<Node> list) {
        if(node==null){
            return;
        }
        dfs(node.left,list);
        list.add(node);
        dfs(node.right,list);
    }

    public static void main(String[] args) {
        JZ36二叉搜索树与双向链表 jz=new JZ36二叉搜索树与双向链表();
        Node node=new Node(1);
        System.out.println(jz.treeToDoublyList(node).val);
    }

    private static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

}
